package org.myorg.v5;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class Tree_fs{
	
	public Tree_fs left;
	public Tree_fs right;
	public Tree_fs parent;
	public FGene5 value;
	int floor = 1;

	public Tree_fs(FGene5 gene, int n) {
		left = null;
		right = null;
		parent = null;
		//value.add(new FGene5(gene));
		value = new FGene5(gene);
		floor = n;
	}

	public Tree_fs(FGene5 gene) {
		left = null;
		right = null;
		parent = null;
		//value.add(new FGene5(gene));
		value = new FGene5(gene);
	}
	public Tree_fs(Tree_fs node) {
		left = node.left;
		right = node.right;
		parent = node.parent;
		//value.add(new FGene5(gene));
		value = new FGene5(node.value);
	}




	public Tree_fs() {
		left = null;
		right = null;
		parent = null;
		value = null;
	}
	protected ArrayList<Tree_fs> travel_tree_ts(Tree_fs tree) {
		ArrayList<Tree_fs> g_set = new ArrayList<Tree_fs>(1);

		if (tree != null) {

			if (tree.left != null) {

				g_set.addAll(travel_tree_ts(tree.left));
			}

			g_set.add(tree);
			if 	(tree.right != null) {

				g_set.addAll(travel_tree_ts(tree.right));
			}
		}

		return g_set;
	}
	protected void tt_add(Tree_fs tree) {


		if (tree != null) {

			if (tree.left != null) {

				tt_add(tree.left);
			}

			tree.floor++;
			if 	(tree.right != null) {
				tt_add(tree.right);
			}
		}
	}

	protected Tree_fs mv_left(Tree_fs node, Tree_fs tree) {
		Tree_fs rt = null;
		if (tree != null){
			Tree_fs tp = tree.parent;
			Tree_fs tmp = null;



			ArrayList<Tree_fs> lg = travel_tree_ts(tree);
			ArrayList<Tree_fs> lg1 = new ArrayList<Tree_fs>(1);
			ArrayList<Tree_fs> lg2 = new ArrayList<Tree_fs>(1);



			for(Tree_fs p:lg) {
				/*
				 * 1   p dominate q
				 * 0   p non-dominate q 
				 *  -1  q dominate p
				 */
				p.parent = null;
				p.left = null;
				p.right = null;
				int dn = dominate(node.value,p.value);
				if (dn == 1 )
					lg2.add(p);
				else if (dn == 0)
					lg1.add(p);
				else if (dn == -1){
					System.out.println("Error: somthing?");
					System.exit(-1);
				}
					
					
			}

			tp.left = null;
			for(Tree_fs p:lg1) {
				tmp = tnds(node.left, p);
				node.left = tmp;
				tmp.parent = node;
				//				node.left = tnds(node.left, p);
			}
			for(Tree_fs p:lg2) {
				tmp = tnds(tp.left, p);
				tp.left = tmp;
				tmp.parent = tp;
			}	
		}
		return rt;

	}


	//tree non-dominated sorting
	public Tree_fs tnds(Tree_fs T, Tree_fs node) {
		Tree_fs nt = new Tree_fs();
		Tree_fs tmp = null;
		if (T == null){
			nt = node;
		} else {
			/*
			 * 1   p dominate q
			 * 0   p non-dominate q 
			 *  -1  q dominate p
			 */
			int dn = dominate(T.value,node.value);
			if (dn == 1){ //p dominate q, so put q into p->right
				node.floor++;
				if (T.right == null) {

					T.right = node;
					node.parent = T;
				}else {
					tmp = tnds(T.right, node);
					T.right = tmp;
					tmp.parent = T;
					//T.right = tnds(T.right, node);
				}
			}
			else if ( dn == 0){ //p non-dominate q
				if (T.left == null) {

					T.left = node;
					node.parent = T;
				} else{
					//node.left = T.left;
					//node.parent = T;
					//T.left = node;
					tmp = tnds(T.left, node);
					T.left = tmp;
					tmp.parent = T;
					//T.left = tnds(T.left, node);
				}
			}else { // q dominate p
				T.floor++;
				//TODO: right tree floor++
				tt_add(T.right);

				node.parent = T.parent;
				node.right = T;
				T.parent = node;
				//TODO: move T.left to tmp.left
				mv_left(node,T.left);
				T = node;

			}
			nt = T;
		}


		return nt;
	}
	/*
	 * 1 p dominate q
	 *  0 p non-dominate q
	 *  -1 q dominate p
	 */
	protected int dominate(FGene5 p, FGene5 q) {
		int d = 0;
		int small = 0, equ = 0, big = 0;
		int gl = p.goals.length;

		for (int i = 0; i < gl; i++) {
			if (p.goals[i] == q.goals[i])
				equ++;
			else if (p.goals[i] < q.goals[i]) {
				small++;
			}else {
				big++;
			}

		}

		if (equ != gl ) {
			if (small + equ == gl) {
				d = 1;	
			} else if (big + equ == gl) {
				d = -1;
			}

		}
		return d;
	}
	/*protected ArrayList<FGene5> travel_tree(Tree_fs tree) {
		ArrayList<FGene5> g_set = new ArrayList<FGene5>(1);

		if (tree != null) {

			if (tree.left != null) {
				tree.value.rank = tree.floor;
				g_set.addAll(travel_tree(tree.left));
			}
			tree.value.rank = tree.floor;
			g_set.add(tree.value);
			if 	(tree.right != null) {
				tree.value.rank = tree.floor;
				g_set.addAll(travel_tree(tree.right));
			}
		}

		return g_set;
	}*/
	/*protected ArrayList<FGene5> travel_tree(Tree_fs tree) {
		ArrayList<FGene5> g_set = new ArrayList<FGene5>(1);

		if (tree != null) {



			if (tree.left != null) {
				tree.value.rank = tree.floor;
				g_set.addAll(travel_tree(tree.left));
			}
			tree.value.rank = tree.floor;
			g_set.add(tree.value);

			if 	(tree.right != null) {
				tree.value.rank = tree.floor;
				g_set.addAll(travel_tree(tree.right));
			}
		}

		return g_set;
	}*/

	protected ArrayList<ArrayList<Tree_fs>> travel_tree(Tree_fs tree) {
		//ArrayList<FGene5> g_set = new ArrayList<FGene5>(1);
		ArrayList<ArrayList<Tree_fs>> F = new ArrayList<ArrayList<Tree_fs>>(1);
		ArrayList<Tree_fs> Left = new ArrayList<Tree_fs>(1);
		ArrayList<Tree_fs> tmp = new ArrayList<Tree_fs>(1);

		int f = 0;
		Tree_fs ep1 = tree;
		for (; ep1 != null && ep1.left != null; ep1 = ep1.left){
			ep1.value.print();
		}

		for (; ep1 != null ; ep1 = ep1.parent) {
			ep1.value.rank = f;
			tmp.add(ep1);
			System.out.println("ep1 is: ");
			ep1.value.print();
		}
		F.add(tmp);
		f++;

		while (!F.get(f-1).isEmpty()) {
			
			System.out.println("\n\n\nwill begin " + f + "rank");
			
			
			//current F
			ArrayList<Tree_fs> cf = F.get(f-1);
			System.out.println("the parent rank is:" + cf.size());
			for (Tree_fs q:cf) {
				q.value.print();
			}

			ArrayList<Tree_fs> nLeft = new ArrayList<Tree_fs>(1);
			tmp = new ArrayList<Tree_fs>(1);

			for (int i = 0; i < cf.size(); i++) {
				//ArrayList<Tree_fs> ntmp = new ArrayList<Tree_fs>(1);
				//stop node
				Tree_fs sp = cf.get(i), ep = cf.get(i).right;
				System.out.println(i + " sp is: ");
				sp.value.print();
				System.out.println(i + "ep is: ");
				if (ep != null ) {
					ep.value.print();
				}
				for (; ep != null && ep.left != null; ep = ep.left){
				}
				System.out.println(i + "after moving the ep is: ");
				if (ep != null ) {
					ep.value.print();
				}
				

				for (; ep != null && ep.value.ID != sp.value.ID; ep = ep.parent) {
					
					
					if (ep.value.ID == sp.value.ID) {
						System.out.println(i + "ep is ");
						ep.value.print();
						System.out.println(i + "sp is ");
						sp.value.print();
						
						if (ep == sp ) {
							System.out.println("ep == sp" );
						} else {
							System.out.println("why ep != sp");
						}
						if (ep.equals(sp) ) {
							System.out.println("ep.equals(sp)" );
						} else {
							System.out.println("why !ep.equals(sp)?");
						}
						
						
						System.exit(-1);	
						
					}
					
					int mark = 0;
					
					System.out.println(i + "the current tmp is: ");
					for (Tree_fs ttt:tmp) {
						ttt.value.print();
					}
					
					for (Iterator<Tree_fs> itr = tmp.iterator();itr.hasNext(); ) {
						Tree_fs q = itr.next();
						
						System.out.println(i + "the current node ep is: ");
						ep.value.print();
						
						int dn = dominate(q.value,ep.value);
						if ( dn == 1) {
							Tree_fs pt = new Tree_fs(ep);
							System.out.println(i + "will add to Left:");
							pt.value.print();
							
							nLeft.add(pt);
							mark = 1;
							break;
						} else if (dn == -1) {
							Tree_fs tq = new Tree_fs(q);
							nLeft.add(tq);
							itr.remove();
							System.out.println(i + "will remove from tmp:");
							tq.value.print();
						}
					}
					if (mark != 1) {
						ep.value.rank = f;
						tmp.add(ep);
					}
				}
//				System.out.println( i + "the tmp is(tree):" + tmp.size());
//				for (Tree_fs q:tmp) {
//					q.value.print();
//				}
//				System.out.println( i + "the ntmp is(tree):" + ntmp.size());
//				for (Tree_fs q:ntmp) {
//					q.value.print();
//				}
				
//				for (Tree_fs p:ntmp) {
//					tmp.remove(p);
//				}
				System.out.println( i + "after remove the tmp is(tree):" + tmp.size());
				for (Tree_fs q:tmp) {
					q.value.print();
				}
			}

			//ArrayList<Integer> rec = new ArrayList<Integer>();
			
			for (Iterator<Tree_fs> Left_it = Left.iterator(); Left_it.hasNext(); ) {
				ArrayList<Tree_fs> ntmp = new ArrayList<Tree_fs>(1);
				int mark = 0;
				Tree_fs p = Left_it.next();
				for (Iterator<Tree_fs> itr = tmp.iterator();itr.hasNext(); ) {
					Tree_fs q = itr.next();
					int dn = dominate(q.value,p.value);
					if ( dn == 1) {
						mark = 1;
						break;
					} else if (dn == -1) {
						nLeft.add(q);
						itr.remove();
					}
				}
				if (mark != 1) {
					System.out.println("will add from Left");
					p.value.print();
					System.out.println("the tmp is:");
					for (Tree_fs tf:tmp) {
						tf.value.print();
					}
					p.value.rank = f;
					tmp.add(p);
				} else {
					nLeft.add(p);
				}
//				for (Tree_fs np:ntmp) {
//					tmp.remove(np);
//				}
			}

			System.out.println("nLeft");
			for (Tree_fs p:nLeft) {
				p.value.print();
			}
			
			System.out.println(Left.size() + " Left before clear");
			for (Tree_fs p:Left) {
				p.value.print();
			}
			
			Left.clear();
			Left.addAll(nLeft);
			
			
			System.out.println(Left.size() + " Left after clear");
			for (Tree_fs p:Left) {
				
							
				p.value.print();
			}
			

			F.add(tmp);
			
			f++;
		}
		//verified(tree,F);
//		for (ArrayList<Tree_fs> tf:F) {
//			for (Tree_fs p:tf) {
//				g_set.add(p.value);
//			}
//		}

		return F;
	}
	
	/*protected ArrayList<FGene5> travel_tree(Tree_fs tree) {
		ArrayList<FGene5> g_set = new ArrayList<FGene5>(1);
		ArrayList<ArrayList<Tree_fs>> F = new ArrayList<ArrayList<Tree_fs>>(1);
		ArrayList<Tree_fs> Left = new ArrayList<Tree_fs>(1);
		ArrayList<Tree_fs> tmp = new ArrayList<Tree_fs>(1);

		int f = 0;
		Tree_fs ep1 = tree;
		for (; ep1 != null && ep1.left != null; ep1 = ep1.left){
			ep1.value.print();
		}

		for (; ep1 != null ; ep1 = ep1.parent) {
			ep1.value.rank = f;
			tmp.add(ep1);
			System.out.println("ep1 is: ");
			ep1.value.print();
		}
		F.add(tmp);
		f++;

		while (!F.get(f-1).isEmpty()) {
			
			System.out.println("\n\n\nwill begin " + f + "rank");
			
			
			//current F
			ArrayList<Tree_fs> cf = F.get(f-1);
			System.out.println("the parent rank is:" + cf.size());
			for (Tree_fs q:cf) {
				q.value.print();
			}

			ArrayList<Tree_fs> nLeft = new ArrayList<Tree_fs>(1);
			tmp = new ArrayList<Tree_fs>(1);

			for (int i = 0; i < cf.size(); i++) {
				//ArrayList<Tree_fs> ntmp = new ArrayList<Tree_fs>(1);
				//stop node
				Tree_fs sp = cf.get(i), ep = cf.get(i).right;
				System.out.println(i + " sp is: ");
				sp.value.print();
				System.out.println(i + "ep is: ");
				if (ep != null ) {
					ep.value.print();
				}
				for (; ep != null && ep.left != null; ep = ep.left){
				}
				System.out.println(i + "after moving the ep is: ");
				if (ep != null ) {
					ep.value.print();
				}
				

				for (; ep != null && ep.value.ID != sp.value.ID; ep = ep.parent) {
					
					
					if (ep.value.ID == sp.value.ID) {
						System.out.println(i + "ep is ");
						ep.value.print();
						System.out.println(i + "sp is ");
						sp.value.print();
						
						if (ep == sp ) {
							System.out.println("ep == sp" );
						} else {
							System.out.println("why ep != sp");
						}
						if (ep.equals(sp) ) {
							System.out.println("ep.equals(sp)" );
						} else {
							System.out.println("why !ep.equals(sp)?");
						}
						
						
						System.exit(-1);	
						
					}
					
					int mark = 0;
					
					System.out.println(i + "the current tmp is: ");
					for (Tree_fs ttt:tmp) {
						ttt.value.print();
					}
					
					for (Iterator<Tree_fs> itr = tmp.iterator();itr.hasNext(); ) {
						Tree_fs q = itr.next();
						
						System.out.println(i + "the current node ep is: ");
						ep.value.print();
						
						int dn = dominate(q.value,ep.value);
						if ( dn == 1) {
							Tree_fs pt = new Tree_fs(ep);
							System.out.println(i + "will add to Left:");
							pt.value.print();
							
							nLeft.add(pt);
							mark = 1;
							break;
						} else if (dn == -1) {
							Tree_fs tq = new Tree_fs(q);
							nLeft.add(tq);
							itr.remove();
							System.out.println(i + "will remove from tmp:");
							tq.value.print();
						}
					}
					if (mark != 1) {
						ep.value.rank = f;
						tmp.add(ep);
					}
				}
//				System.out.println( i + "the tmp is(tree):" + tmp.size());
//				for (Tree_fs q:tmp) {
//					q.value.print();
//				}
//				System.out.println( i + "the ntmp is(tree):" + ntmp.size());
//				for (Tree_fs q:ntmp) {
//					q.value.print();
//				}
				
//				for (Tree_fs p:ntmp) {
//					tmp.remove(p);
//				}
				System.out.println( i + "after remove the tmp is(tree):" + tmp.size());
				for (Tree_fs q:tmp) {
					q.value.print();
				}
			}

			//ArrayList<Integer> rec = new ArrayList<Integer>();
			
			for (Iterator<Tree_fs> Left_it = Left.iterator(); Left_it.hasNext(); ) {
				ArrayList<Tree_fs> ntmp = new ArrayList<Tree_fs>(1);
				int mark = 0;
				Tree_fs p = Left_it.next();
				for (Iterator<Tree_fs> itr = tmp.iterator();itr.hasNext(); ) {
					Tree_fs q = itr.next();
					int dn = dominate(q.value,p.value);
					if ( dn == 1) {
						mark = 1;
						break;
					} else if (dn == -1) {
						nLeft.add(q);
						itr.remove();
					}
				}
				if (mark != 1) {
					System.out.println("will add from Left");
					p.value.print();
					System.out.println("the tmp is:");
					for (Tree_fs tf:tmp) {
						tf.value.print();
					}
					p.value.rank = f;
					tmp.add(p);
				} else {
					nLeft.add(p);
				}
//				for (Tree_fs np:ntmp) {
//					tmp.remove(np);
//				}
			}

			System.out.println("nLeft");
			for (Tree_fs p:nLeft) {
				p.value.print();
			}
			
			System.out.println(Left.size() + " Left before clear");
			for (Tree_fs p:Left) {
				p.value.print();
			}
			
			Left.clear();
			Left.addAll(nLeft);
			
			
			System.out.println(Left.size() + " Left after clear");
			for (Tree_fs p:Left) {
				
							
				p.value.print();
			}
			

			F.add(tmp);
			
			f++;
		}
		//verified(tree,F);
		for (ArrayList<Tree_fs> tf:F) {
			for (Tree_fs p:tf) {
				g_set.add(p.value);
			}
		}

		return g_set;
	}*/



	private void verified(Tree_fs tree, ArrayList<ArrayList<Tree_fs>> F) {
		int pn = 0;
		for (ArrayList<Tree_fs> f:F) {
			pn += f.size();
		}
		boolean wrong[] = new boolean[pn];
		int i = 0;
		for (ArrayList<Tree_fs> f:F) {
			for (Tree_fs p:f){
				for (ArrayList<Tree_fs> f2:F) {
					for (Tree_fs q:f2){
						if (dominate(q.value,p.value) == 1 && (q.value.rank >= p.value.rank)) {
							wrong[i] = true;
							System.out.println("p and q is:");
							q.value.print();
							p.value.print();

							int j = 0;
							for (ArrayList<Tree_fs> f3:F) {
								System.out.print("rank " + j);
								for (Tree_fs r:f3){
									r.value.print();
								}
								j++;
							}

							try {
								Thread.sleep(1);
							} catch (InterruptedException e) {
								// TODO Auto-generated catch block
								e.printStackTrace();
							}
							System.exit(-1);
						}
					}
				}
				i++;
			}
		}
	}

	/*
	 * crowd degree
	 * 0 minimal crowd degree
	 * inf maximal crowd degree
	 * 
	 * crowd_degree = sum(1/reg_distance(i)) i = 1,...,goals_num
	 * 
	 * reg_distance(i) = distance(i)/max_dis(i) 
	 *  
	 */

	public void crowd(List<FGene5> nl) {
		//initial crowd
		System.out.println("before rank and crowd:");
		for (FGene5 q:nl) {
			q.crowd = 0;
			q.print();
		}

		int goals_num = nl.get(0).goals.length;
		for (int i =0 ; i < goals_num; i++) {
			CompareGoals com = new CompareGoals(i);
			Collections.sort(nl,com);

			int l = nl.size();

			nl.get(0).crowd = Double.MAX_VALUE;
			nl.get(l-1).crowd = Double.MAX_VALUE;



			double max_dis = nl.get(l-1).goals[i] - nl.get(0).goals[i];

			if (max_dis != 0){
				for (int j = l-2; j > 0; j--){
					nl.get(j).crowd = nl.get(j).crowd + (nl.get(j+1).goals[i] - nl.get(j-1).goals[i])/max_dis;
				}
			} 
			System.out.println("crowd: ");
			for (FGene5 q:nl) {
				q.print();
			}

		}

		System.out.println("rank and crowd:");
		for (FGene5 q:nl) {
			q.print();
		}
	}
	public ArrayList<FGene5> choose(ArrayList<ArrayList<Tree_fs>> lg, int pn) {
		
		ArrayList<FGene5> rl = new ArrayList<FGene5>(pn/2);
		// list size
		int ls = lg.size();
		
		Iterator it =  lg.iterator();
		int cs = 0;
		
		while(it.hasNext()) {
			ArrayList<Tree_fs> cr = (ArrayList<Tree_fs>) it.next();
			cs += cr.size();
			if (cs <= pn/2) {
				for (Tree_fs p:cr) {
					rl.add(p.value);
				}
				if (cs == pn/2) {
					break;
				}
			} else {
				List<FGene5> g_set = new ArrayList<FGene5>(cr.size());
				for (Tree_fs p:cr) {
					g_set.add(p.value);
				}
				crowd(g_set);
				CompareGoals rk = new CompareGoals(-1);
				Collections.sort(g_set,rk);
				for (int i = g_set.size() - 1; rl.size() < pn/2; i--) {
					rl.add(g_set.get(i));
				}
				break;
			}
		}

		return rl;
	}
	
	/*public ArrayList<FGene5> choose(ArrayList<FGene5> lg) {
		// list size
		int ls = lg.size();
		// current rank
		int c_r = 0;

		CompareGoals com = new CompareGoals(-2);
		Collections.sort(lg,com);

		System.out.println("before chosen: ");
		int count = 0;
		for (FGene5 q:lg) {
			System.out.print(count + "\t");

			q.print();
			count++;
		}

		ArrayList<FGene5> rl = new ArrayList<FGene5>(ls/2);
		//int cur = 0;
		int start = 0, end = 1;
		while (start < ls/2) {
			for (int i = start; i < ls - 1; i++) {


				//lg.get(i).rank = c_r;
				if (lg.get(i).rank < lg.get(i + 1).rank) {

					System.out.println(i + " two gene");
					lg.get(i).print();
					lg.get(i+1).print();


					//c_r++;
					end = i+1;
					break;
				}
				end = i+1;
			}
			//if (end != start) {

			System.out.println("start: " + start + " end: " + end);

			List<FGene5> nl = lg.subList(start, end);
			crowd(nl);

			//System.out.println("same rank people:");
			//			for (FGene5 q:nl) {
			//				q.print();
			//			}
			CompareGoals rk = new CompareGoals(-1);
			Collections.sort(nl,rk);

			if (rl.size() + (end - start) <= ls/2) {
				//System.out.println("new people:");

				for (int i = 0; i < nl.size(); i++) {
					rl.add(nl.get(i));
					//nl.get(i).print();
				}
			}else {
				for (int i = nl.size() - 1; rl.size() < ls/2; i--) {
					rl.add(nl.get(i));
					//nl.get(i).print();
				}
			}
			//}else {
			//	rl.add(lg.get(start));
			//}


			start = end;
			end = end + 1;
		}

		//System.out.println("after sorting: ");
		//		for (FGene5 q:lg) {
		//			q.print();
		//		}

		//System.out.println("after chosen: ");
		//		for (FGene5 q:rl) {
		//			q.print();
		//		}

		return rl;
	}*/
	


	public void print_tree(Tree_fs tree,int n) {
		if (tree != null) {
			for(int i = 0;i < n; i++) System.out.print(n + "-");
			System.out.print(tree.floor);
			tree.value.print();
			n++;
			if (tree.left != null) {
				print_tree(tree.left, n);
			}
			//System.out.print("-");
			if 	(tree.right != null) {
				print_tree(tree.right, n);
			}
		}

	}

	public FPeople5 td(FPeople5 p) {
		Tree_fs tree = null;
		int pn = p.p_num;
		for (int i = 0; i < pn; i++) {
			
			FGene5 g = p.getPersons()[i];
			g.set_ID(i);
			tree = tnds(tree, new Tree_fs(g,0));
		}
		System.out.println("tree is");
		print_tree(tree,1);


		ArrayList<ArrayList<Tree_fs>> lg = travel_tree(tree);


		 ArrayList<FGene5> rp = choose(lg,pn);

		FPeople5 np = new FPeople5(rp.size());
		for (int i = 0; i < np.p_num; i++) {
			np.persons[i] = new FGene5(rp.get(i));
		}
		return np;
	}

}



